package 题目集.拓扑排序;

import org.junit.Test;

import java.util.Arrays;

/**
 * 一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
 * 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
 * 给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
 * https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
 */
public class ch04_参加会议的最多员工数 {
    /**
     * 这题是一个贪心题，直接说贪心策略。
     * 这题有两种情况：
     *     一种是选多个小环的情况、一种是选一个大环的情况。小环可以存在多个，大环只能存在一个（有大环就不能有其他环）。
     *      答案即是 所有小环的员工数以及他们的最长链之和 与 大环的员工数中较大的一个。
     * 通过拓扑排序筛选出环和他们链条的最大长度，再判断环是大环还是小环。
     */
    public int maximumInvitations(int[] favorite) {
        int[] inDeg = new int[favorite.length];   //记录每个员工的入度
        int[] size = new int[favorite.length];    //记录每个员工的最长链
        Arrays.fill(size, 1);
        for (int i = 0; i < favorite.length; i++) {
            inDeg[favorite[i]]++;
        }
        int[] queue = new int[favorite.length];
        int head = 0, tail = 0;
        for (int i = 0; i < inDeg.length; i++) {
            if (inDeg[i] == 0) {
                queue[tail++] = i;
            }
        }
        while (head < tail) {       //拓扑排序,求出每个员工的最长链。并筛出环
            int cur = queue[head++];
            int next = favorite[cur];
            size[next] = Math.max(size[next], size[cur] + 1);
            inDeg[next]--;
            if (inDeg[next] == 0) {
                queue[tail++] = next;
            }
        }
        int smallSize = 0, moreSize = 0;
        for (int i = 0; i < favorite.length; i++) {
            if (inDeg[i] != 0) {
                int ringSize = 1;
                inDeg[i] = 0;
                for (int j = favorite[i]; j != i; j = favorite[j]) {    //求出环的大小
                    ringSize++;
                    size[i] += size[j];
                    inDeg[j] = 0;
                }
                if (ringSize == 2) {    //小环可共存
                    smallSize += size[i];
                } else {    //大环只能存在一个
                    moreSize = Math.max(moreSize, ringSize);
                }
            }
        }
        return Math.max(smallSize, moreSize);
    }

    @Test
    public void test() {
        System.out.println(maximumInvitations(new int[]{0,3,4,2,5,3,8,4,6,9}));
    }
}
